home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 15 / CU Amiga Magazine's Super CD-ROM 15 (1997)(EMAP Images)(GB)[!][issue 1997-10].iso / CUCD / Graphics / Ghostscript / source / istack.c < prev    next >
C/C++ Source or Header  |  1996-03-20  |  15KB  |  486 lines
  1. /* Copyright (C) 1992, 1995, 1996 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* istack.c */
  20. /* Ghostscript expandable stack manager */
  21. #include "memory_.h"
  22. #include "ghost.h"
  23. #include "gsstruct.h"
  24. #include "gsutil.h"
  25. #include "errors.h"
  26. #include "ialloc.h"
  27. #include "istack.h"
  28. #include "istruct.h"        /* for gs_reloc_refs */
  29. #include "iutil.h"
  30. #include "ivmspace.h"        /* for local/global test */
  31. #include "store.h"
  32.  
  33. /* Forward references */
  34. private void init_block(P3(ref_stack *, ref *, uint));
  35. int ref_stack_push_block(P3(ref_stack *, uint, uint));
  36.  
  37. /* GC procedures */
  38. #define sptr ((ref_stack *)vptr)
  39. private CLEAR_MARKS_PROC(ref_stack_clear_marks) {
  40.     r_clear_attrs(&sptr->current, l_mark);
  41. }
  42. private ENUM_PTRS_BEGIN(ref_stack_enum_ptrs) return 0;
  43.     case 0:
  44.         *pep = &sptr->current;
  45.         return ptr_ref_type;
  46. ENUM_PTRS_END
  47. private RELOC_PTRS_BEGIN(ref_stack_reloc_ptrs) {
  48. #if stacks_are_segmented
  49.     /* In a segmented environment, the top block can't move, */
  50.     /* so we don't need to relocate pointers to it. */
  51. #else
  52.     /* Note that the relocation must be a multiple of sizeof(ref_packed) */
  53.     /* * align_packed_per_ref, but it need not be a multiple of */
  54.     /* sizeof(ref).  Therefore, we must do the adjustments using */
  55.     /* ref_packed pointers rather than ref pointers. */
  56.     ref_packed *bot = (ref_packed *)sptr->current.value.refs;
  57.     long reloc;
  58.     gs_reloc_refs((ref_packed *)&sptr->current,
  59.               (ref_packed *)(&sptr->current + 1),
  60.               gcst);
  61.     r_clear_attrs(&sptr->current, l_mark);
  62.     reloc = bot - (ref_packed *)sptr->current.value.refs;
  63. #define reloc_p(p)\
  64.   sptr->p = (ref *)((ref_packed *)sptr->p - reloc);
  65.     reloc_p(p);
  66.     reloc_p(bot);
  67.     reloc_p(top);
  68. #undef reloc_p
  69. #endif
  70. } RELOC_PTRS_END
  71. /* Structure type for a ref_stack. */
  72. public_st_ref_stack();
  73.  
  74. /* Initialize a stack. */
  75. void
  76. ref_stack_init(register ref_stack *pstack, ref *psb,
  77.   uint bot_guard, uint top_guard, ref *pguard, gs_ref_memory_t *mem)
  78. {    uint size = r_size(psb);
  79.     uint avail = size - (stack_block_refs + bot_guard + top_guard);
  80.     ref_stack_block *pblock = (ref_stack_block *)psb->value.refs;
  81.     s_ptr body = (s_ptr)(pblock + 1);
  82.     pstack->bot = body + bot_guard;
  83.     pstack->p = pstack->bot - 1;
  84.     pstack->top = pstack->p + avail;
  85.     pstack->current = *psb;
  86.     pstack->extension_size = 0;
  87.     pstack->extension_used = 0;
  88.  
  89.     make_int(&pstack->max_stack, avail);
  90.     pstack->requested = 0;
  91.  
  92.     pstack->bot_guard = bot_guard;
  93.     pstack->top_guard = top_guard;
  94.     pstack->block_size = size - segmented_guard(bot_guard + top_guard);
  95.     pstack->body_size = avail;
  96.     if ( pguard != 0 )
  97.       pstack->guard_value = *pguard;
  98.     else
  99.       make_tav(&pstack->guard_value, t__invalid, 0, intval, 0);
  100.     pstack->underflow_error = -1;        /* bogus, caller must set */
  101.     pstack->overflow_error = -1;        /* bogus, caller must set */
  102.     pstack->allow_expansion = true;        /* default, caller may reset */
  103.     pstack->memory = mem;
  104.     init_block(pstack, psb, 0);
  105.     refset_null(pstack->bot, avail);
  106.     make_empty_array(&pblock->next, 0);
  107. }
  108.  
  109. /* Set the maximum number of elements allowed on a stack. */
  110. int
  111. ref_stack_set_max_count(ref_stack *pstack, long nmax)
  112. {    uint nmin = pstack->extension_size + (pstack->top - pstack->bot + 1);
  113.     if ( nmax < nmin )
  114.       nmax = nmin;
  115.     if ( nmax > max_uint / sizeof(ref) )
  116.       nmax = max_uint / sizeof(ref);
  117.     if ( !pstack->allow_expansion )
  118.       {    uint ncur = pstack->body_size;
  119.         if ( nmax > ncur )
  120.           nmax = ncur;
  121.       }
  122.     pstack->max_stack.value.intval = nmax;
  123.     return 0;
  124. }
  125.  
  126. /* Return the number of elements on a stack. */
  127. uint
  128. ref_stack_count(const ref_stack *pstack)
  129. {    return pstack->extension_used + (pstack->p - pstack->bot + 1);
  130. }
  131.  
  132. /* Retrieve a given element from the stack, counting from */
  133. /* 0 as the top element. */
  134. ref *
  135. ref_stack_index(const ref_stack *pstack, long idx)
  136. {    ref_stack_block *pblock;
  137.     uint used = pstack->p + 1 - pstack->bot;
  138.     if ( idx < 0 )
  139.         return NULL;
  140.     if ( idx < used )        /* common case */
  141.         return pstack->p - (uint)idx;
  142.     pblock = (ref_stack_block *)pstack->current.value.refs;
  143.     do
  144.     {    pblock = (ref_stack_block *)pblock->next.value.refs;
  145.         if ( pblock == 0 )
  146.             return NULL;
  147.         idx -= used;
  148.         used = r_size(&pblock->used);
  149.     }
  150.     while ( idx >= used );
  151.     return pblock->used.value.refs + (used - 1 - (uint)idx);
  152. }
  153.  
  154. /* Count the number of elements down to and including the first mark. */
  155. /* If no mark is found, return 0. */
  156. uint
  157. ref_stack_counttomark(const ref_stack *pstack)
  158. {    uint scanned = 0;
  159.     STACK_LOOP_BEGIN(pstack, p, used)
  160.     {    uint count = used;
  161.         p += used - 1;
  162.         for ( ; count; count--, p-- )
  163.           if ( r_has_type(p, t_mark) )
  164.             return scanned + (used - count + 1);
  165.         scanned += used;
  166.     }
  167.     STACK_LOOP_END(p, used)
  168.     return 0;
  169. }
  170.  
  171. /* Store the top elements of a stack into an array, */
  172. /* with or without store/undo checking. */
  173. /* May return e_rangecheck or e_invalidaccess. */
  174. int
  175. ref_stack_store(const ref_stack *pstack, ref *parray, uint count, uint skip,
  176.   int age, bool check, client_name_t cname)
  177. {    uint left, pass;
  178.     ref *to;
  179.     uint space = r_space(parray);
  180.     if ( count > ref_stack_count(pstack) || count > r_size(parray) )
  181.       return_error(e_rangecheck);
  182.     if ( check && space != avm_local )
  183.       {    /* Pre-check the elements being stored. */
  184.         left = count, pass = skip;
  185.         STACK_LOOP_BEGIN(pstack, ptr, size)
  186.           if ( size <= pass )
  187.             pass -= size;
  188.           else
  189.             {    int code;
  190.             if ( pass != 0 )
  191.               size -= pass, pass = 0;
  192.             ptr += size;
  193.             if ( size > left )
  194.               size = left;
  195.             left -= size;
  196.             code = refs_check_space(ptr - size, size, space);
  197.             if ( code < 0 )
  198.               return code;
  199.             if ( left == 0 )
  200.               break;
  201.             }
  202.         STACK_LOOP_END(ptr, size)
  203.       }
  204.     to = parray->value.refs + count;
  205.     left = count, pass = skip;
  206.     STACK_LOOP_BEGIN(pstack, from, size)
  207.       if ( size <= pass )
  208.         pass -= size;
  209.       else
  210.         { if ( pass != 0 )
  211.         size -= pass, pass = 0;
  212.           from += size;
  213.           if ( size > left )
  214.         size = left;
  215.           left -= size;
  216.           switch ( age )
  217.         {
  218.         case -1:    /* not an array */
  219.           while ( size-- )
  220.             { from--, to--;
  221.               ref_assign(to, from);
  222.             }
  223.           break;
  224.         case 0:        /* old array */
  225.           while ( size-- )
  226.             { from--, to--;
  227.               ref_assign_old(parray, to, from, cname);
  228.             }
  229.           break;
  230.         case 1:        /* new array */
  231.           while ( size-- )
  232.             { from--, to--;
  233.               ref_assign_new(to, from);
  234.             }
  235.           break;
  236.         }
  237.           if ( left == 0 )
  238.         break;
  239.         }
  240.     STACK_LOOP_END(from, size)
  241.     r_set_size(parray, count);
  242.     return 0;
  243. }
  244.  
  245. /* Pop a given number of elements off a stack. */
  246. /* The number must not exceed the number of elements in use. */
  247. void
  248. ref_stack_pop(register ref_stack *pstack, uint count)
  249. {    uint used;
  250.     while ( (used = pstack->p + 1 - pstack->bot) < count )
  251.     {    count -= used;
  252.         pstack->p = pstack->bot - 1;
  253.         ref_stack_pop_block(pstack);
  254.     }
  255.     pstack->p -= count;
  256. }
  257.  
  258. /* Pop the top block off a stack. */
  259. int
  260. ref_stack_pop_block(register ref_stack *pstack)
  261. {    s_ptr bot = pstack->bot;
  262.     uint count = pstack->p + 1 - bot;
  263.     ref_stack_block *pcur =
  264.       (ref_stack_block *)pstack->current.value.refs;
  265.     register ref_stack_block *pnext =
  266.       (ref_stack_block *)pcur->next.value.refs;
  267.     uint used;
  268.     ref *body;
  269.     ref next;
  270.     if ( pnext == 0 )
  271.       return_error(pstack->underflow_error);
  272.     used = r_size(&pnext->used);
  273.     body = (ref *)(pnext + 1) + flat_guard(pstack->bot_guard);
  274.     next = pcur->next;
  275.     /*
  276.      * If we're on a segmented system, the top block does not move,
  277.      * so we move up the used part of the top block, copy the contents
  278.      * of the next block under it, and free the next block.
  279.      * We also do this on non-segmented systems if the contents of the
  280.      * two blocks won't fit in a single block; in this case we copy up
  281.      * as much as will fit.  On non-segmented systems where the contents
  282.      * of both blocks fit in a single block, we copy the used part
  283.      * of the top block to the top of the next block, and free
  284.      * the top block.
  285.      */
  286.     if ( used + count > pstack->body_size )
  287.       {    /* Move as much into the top block as will fit. */
  288.         uint moved = pstack->body_size - count;
  289.         uint left;
  290.         if ( moved == 0 )
  291.           return_error(e_Fatal);
  292.         memmove(bot + moved, bot, count * sizeof(ref));
  293.         left = used - moved;
  294.         memcpy(bot, body + left, moved * sizeof(ref));
  295.         refset_null(body + left, moved);
  296.         r_dec_size(&pnext->used, moved);
  297.         pstack->p = pstack->top;
  298.         pstack->extension_used -= moved;
  299.       }
  300.     else
  301.       {
  302. #if stacks_are_segmented
  303.     /* We know there are no guard elements in the next block. */
  304.     memmove(bot + used, bot, count * sizeof(ref));
  305.     memcpy(bot, body, used * sizeof(ref));
  306.     pcur->next = pnext->next;
  307.     gs_free_ref_array(pstack->memory, &next, "ref_stack_pop_block");
  308. #else
  309.     memcpy(body + used, bot, count * sizeof(ref));
  310.     pstack->bot = bot = body;
  311.     pstack->top = bot + pstack->body_size - 1;
  312.     gs_free_ref_array(pstack->memory, &pstack->current,
  313.               "ref_stack_pop_block");
  314.     pstack->current = next;
  315. #endif
  316.     pstack->p = bot + (used + count - 1);
  317.     pstack->extension_size -= pstack->body_size;
  318.     pstack->extension_used -= used;
  319.       }
  320.     return 0;
  321. }
  322.  
  323. /* Extend a stack to recover from an overflow condition. */
  324. /* May return overflow_error or e_VMerror. */
  325. int
  326. ref_stack_extend(ref_stack *pstack, uint request)
  327. {    uint keep = (pstack->top - pstack->bot + 1) / 3;
  328.     uint count = pstack->p - pstack->bot + 1;
  329.  
  330.     if ( pstack->p < pstack->bot )
  331.       {    /* Adding another block can't help things. */
  332.         return_error(pstack->overflow_error);
  333.       }
  334.     if ( keep + request > pstack->body_size )
  335.       keep = pstack->body_size - request;
  336.     if ( keep > count )
  337.       keep = count;        /* required by ref_stack_push_block */
  338.     return ref_stack_push_block(pstack, keep, request);
  339. }
  340.  
  341. /* Push N empty slots onto a stack.  These slots are not initialized; */
  342. /* the caller must fill them immediately.  May return overflow_error */
  343. /* (if max_stack would be exceeded, or the stack has no allocator) */
  344. /* or e_VMerror. */
  345. int
  346. ref_stack_push(register ref_stack *pstack, uint count)
  347. {    /* Don't bother to pre-check for overflow: we must be able to */
  348.     /* back out in the case of a VMerror anyway, and */
  349.     /* ref_stack_push_block will make the check itself. */
  350.     uint needed = count;
  351.     uint added;
  352.     for ( ; (added = pstack->top - pstack->p) < needed; needed -= added )
  353.       {    int code;
  354.         pstack->p = pstack->top;
  355.         code =
  356.           ref_stack_push_block(pstack,
  357.                        (pstack->top - pstack->bot + 1) / 3,
  358.                        count);
  359.         if ( code < 0 )
  360.           {    /* Back out. */
  361.             ref_stack_pop(pstack, count - needed);
  362.             pstack->requested = count;
  363.             return code;
  364.           }
  365.       }
  366.     pstack->p += needed;
  367.     return 0;
  368. }
  369.  
  370. /* Push a block onto the stack, specifying how many elements of */
  371. /* the current top block should remain in the top block and also */
  372. /* how many elements we are trying to add. */
  373. /* May return overflow_error or e_VMerror. */
  374. /* Must have keep <= count. */
  375. int
  376. ref_stack_push_block(register ref_stack *pstack, uint keep, uint add)
  377. {    uint count = pstack->p - pstack->bot + 1;
  378.     uint move = count - keep;
  379.     ref_stack_block *pcur = (ref_stack_block *)pstack->current.value.refs;
  380.     ref next;
  381.     ref_stack_block *pnext;
  382.     ref *body;
  383.     int code;
  384.     if ( keep > count )
  385.       return_error(e_Fatal);
  386.     /* Check for overflowing the maximum size, */
  387.     /* or expansion not allowed.  */
  388.     if ( pstack->memory == 0 ||
  389.          pstack->extension_used + (pstack->top - pstack->bot) + add >=
  390.            pstack->max_stack.value.intval ||
  391.          !pstack->allow_expansion
  392.        )
  393.       return_error(pstack->overflow_error);
  394.     code = gs_alloc_ref_array(pstack->memory, &next, 0,
  395.                   pstack->block_size, "ref_stack_push_block");
  396.     if ( code < 0 )
  397.       return code;
  398.     pnext = (ref_stack_block *)next.value.refs;
  399.     body = (ref *)(pnext + 1);
  400. #if stacks_are_segmented
  401.     /* Copy all but the top keep elements into the new block, */
  402.     /* and move the top elements down. */
  403.     /* We know there are no guard elements in the new block. */
  404.     memcpy(body, pstack->bot, move * sizeof(ref));
  405.     /* Clear the elements above the top of the new block. */
  406.     refset_null(body + move, pstack->body_size - move);
  407.     if ( keep <= move )
  408.     {    /* No overlap, memcpy is safe. */
  409.         memcpy(pstack->bot, pstack->bot + move, keep * sizeof(ref));
  410.     }
  411.     else
  412.     {    uint i;
  413.         s_ptr bot = pstack->bot;
  414.         s_ptr up = bot + move;
  415.         for ( i = 0; i < keep; i++ )
  416.             bot[i] = up[i];
  417.     }
  418.     pnext->next = pcur->next;
  419.     pnext->used = next;
  420.     pcur->next = next;
  421.     pnext->used.value.refs = body;
  422.     r_set_size(&pnext->used, move);
  423. #else
  424.     /* Copy the top keep elements into the new block, */
  425.     /* and make the new block the top block. */
  426.     init_block(pstack, &next, keep);
  427.     body += pstack->bot_guard;
  428.     memcpy(body, pstack->bot + move, keep * sizeof(ref));
  429.     /* Clear the elements above the top of the new block. */
  430.     refset_null(body + keep, pstack->body_size - keep);
  431.     /* Clear the elements above the top of the old block. */
  432.     refset_null(pstack->bot + move, keep);
  433.     pnext->next = pstack->current;
  434.     pcur->used.value.refs = pstack->bot;
  435.     r_set_size(&pcur->used, move);
  436.     pstack->current = next;
  437.     pstack->bot = body;
  438.     pstack->top = pstack->bot + pstack->body_size - 1;
  439. #endif
  440.     pstack->p = pstack->bot + keep - 1;
  441.     pstack->extension_size += pstack->body_size;
  442.     pstack->extension_used += move;
  443.     return 0;
  444. }
  445.  
  446. /* Clean up a stack for garbage collection. */
  447. void
  448. ref_stack_cleanup(ref_stack *pstack)
  449. {    ref_stack_block *pblock =
  450.       (ref_stack_block *)pstack->current.value.refs;
  451.     refset_null(pstack->p + 1, pstack->top - pstack->p);
  452.     pblock->used = pstack->current;        /* set attrs */
  453.     pblock->used.value.refs = pstack->bot;
  454.     r_set_size(&pblock->used, pstack->p + 1 - pstack->bot);
  455. }
  456.  
  457. /* ------ Internal routines ------ */
  458.  
  459. /* Initialize the guards and body of a stack block. */
  460. /* Note that this always initializes the guards, so it should not be used */
  461. /* for extension blocks in a segmented environments. */
  462. private void
  463. init_block(ref_stack *pstack, ref *psb, uint used)
  464. {    ref *brefs = psb->value.refs;
  465. #define pblock ((ref_stack_block *)brefs)
  466.     register uint i;
  467.     register ref *p;
  468.     for ( i = pstack->bot_guard, p = brefs + stack_block_refs;
  469.           i != 0; i--, p++
  470.         )
  471.         ref_assign(p, &pstack->guard_value);
  472.     /* The top guard elements will never be read, */
  473.     /* but we need to initialize them for the sake of the GC. */
  474.     /* We can use refset_null for this, because even though it uses */
  475.     /* make_null_new and stack elements must not be marked new, */
  476.     /* these slots will never actually be read or written. */
  477.     if ( pstack->top_guard )
  478.       {    ref *top = brefs + r_size(psb);
  479.         int top_guard = pstack->top_guard;
  480.         refset_null(top - top_guard, top_guard);
  481.       }
  482.     pblock->used = *psb;
  483.     pblock->used.value.refs = brefs + stack_block_refs + pstack->bot_guard;
  484.     r_set_size(&pblock->used, 0);
  485. }
  486.